package com.mzy;

import com.mzy.utils.Utils;
import jdk.nashorn.internal.ir.ReturnNode;

import java.lang.reflect.Parameter;
import java.security.cert.PolicyQualifierInfo;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;

import static com.mzy.utils.Utils.swap;


/**
 * @Author: codermzy
 * @Date: 2024/02/03/19:02
 * @Description:
 */
public class QuickSort {

    /*
    public static void test(Integer[] arr, int num) {
        int ltIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <= num) {
                Utils.swap(arr, ++ltIndex, i);
            }
        }
    }

    public static void near(Integer[] arr, int L, int R) {
        int less = L - 1;
        int more = R;
        int num = arr[R];
        int index = L;
        while (index <= more) {
            if (arr[index] == num) {
                index++;
            } else if (arr[index] < num) {
                Utils.swap(arr, ++less, index++);
            } else if (arr[index] > num) {
                Utils.swap(arr, more--, index);
            }
        }
        Utils.swap(arr, more, R);

    }
    */


/*    public static void sort(Integer[] arr) {

        // 1 4 6 9 10 2 3 5 8 7
        // 7 为 pivot，比 7 大 的放右边，比7小的放左边
        // 1 4 6 9 10 2 3 5 8 7
        // i                j p


        partition(arr, 0, arr.length - 1);


    }

    private static void partition(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int i = left, j = right - 1;
        int pivot = arr[right];

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (j >= 0 && arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                Utils.swap(arr, i, j);
                i++;
                j--;
            }
        }

        Utils.swap(arr, i, right);

        partition(arr, left, j);
        partition(arr, i + 1, right);
    }*/


 /*   public static void sort(Integer[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int i = left, j = right - 1;
        int pivot = arr[right];
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (j >= 0 && arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                Utils.swap(arr, i, j);
                i++;
                j--;
            }
        }

        Utils.swap(arr, i, right);

        quickSort(arr, left, j);
        quickSort(arr, i + 1, right);
    }*/

   /* public static void test(Integer[] arr) {
        partition(arr, 0, arr.length - 1);
    }

    private static void partition(Integer[] arr, int left, int right) {
        if (left >= right) return;
        int pivot = arr[right];
        int i = left, j = right - 1;

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (j >= 0 && arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                Utils.swap(arr, i, j);
                i++;
                j--;
            }
        }
        Utils.swap(arr, i, right);
        partition(arr, left, j);
        partition(arr, i + 1, right);
    }*/

/*    private static void partition(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[right];
        int i = left, j = right - 1;

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (j >= 0 && arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                Utils.swap(arr, i, j);
                i++;
                j--;
            }
        }
        Utils.swap(arr, i, right);

        partition(arr, left, j);
        partition(arr, i + 1, right);

    }*/

    /*public static void test(Integer[] arr) {
        partition(arr, 0, arr.length - 1);
    }

    private static void partition(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[right];
        int i = left;
        int j = right - 1;

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (j >= 0 && arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                Utils.swap(arr, i, j);
                i++;
                j--;
            }
        }

        Utils.swap(arr, i, right);
        partition(arr, left, j);
        partition(arr, i + 1, right);
    }


*/
    // private static void partition(Integer[] arr, int left, int right) {
    //     if (left >= right) return;
    //
    //     int i = left, j = right - 1;
    //     int pivot = arr[right];
    //
    //
    //     while (i <= j) {
    //         while (pivot > arr[i]) {
    //             i++;
    //         }
    //
    //         while (j >= 0 && pivot < arr[j]) {
    //             j--;
    //         }
    //
    //         if (i <= j) {
    //             Utils.swap(arr, i, j);
    //             i++;
    //             j--;
    //         }
    //     }
    //
    //     Utils.swap(arr, i, right);
    //     partition(arr, left, j);
    //     partition(arr, i + 1, right);
    // }

    /*private static void partition(Integer[] arr, int left, int right) {
        if (left >= right) return;
        int pivot = arr[right];
        int i = left, j = right - 1;

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (j >= 0 && arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                Utils.swap(arr, i, j);
                i++;
                j--;
            }
        }

        Utils.swap(arr, i, right);
        partition(arr, left, j);
        partition(arr, i + 1, right);

    }*/

/*    public static void test(Integer[] arr) {
        partition(arr, 0, arr.length - 1);
    }

    private static void partition(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[right];
        int i = left, j = right - 1;

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (j >= 0 && arr[j] > pivot) {
                j--;
            }

            if(i <= j){
                Utils.swap(arr, i, j);
                i++;
                j--;
            }
        }
        Utils.swap(arr, i, right);

        partition(arr, left, j);
        partition(arr, i + 1 , right);
    }*/

    // private static void partition(Integer[] arr, int left, int right) {
    //     if (left >= right) return;
    //
    //     int pivot = arr[right];
    //
    //     int i = left;
    //     int j = right - 1;
    //     while (i <= j) {
    //         while (pivot > arr[i]) {
    //             i++;
    //         }
    //         while (j >= 0 && pivot < arr[j]) {
    //             j--;
    //         }
    //
    //         if (i <= j) {
    //             Utils.swap(arr, i, j);
    //             i++;
    //             j--;
    //         }
    //     }
    //
    //     Utils.swap(arr, i, right);
    //     partition(arr, left, j);
    //     partition(arr, i + 1, right);
    //
    // }

    public static void main(String[] args) {
        // 3 9 10 5 2
        // 2 9 10 5 3
        // i        p
        // j

        // 2 9 10 5 3
        // 2 3 10 5 9
        //   i      p
        // j


        // 2 3 10 5 9
        // 2 3 5 10 9
        //       i  p
        //     j


        // 2 3 10 5 9
        // 2 3 5  9 10
        //           p
        //           i
        //         j
        Integer[] arr = {5, 2, 3, 1};

        test(arr);
        Utils.testSort(QuickSort::test);
        // sortDescending(arr);

        // test(arr, 3);
        System.out.println(Arrays.toString(arr));
        // near(arr, 0, arr.length - 1);
        // System.out.println(Arrays.toString(arr));
    }

    private static void test(Integer[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(Integer[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = arr[right];
        int i = left, j = right - 1;
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (j >= 0 && arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        swap(arr, i, right);
        quickSort(arr, left, j);
        quickSort(arr, i + 1, right);
    }

    /*private static void test(Integer[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[right];
        int i = left, j = right - 1;

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (j >= 0 && arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        swap(arr, i, right);
        quickSort(arr, left, j);
        quickSort(arr, i + 1, right);
    }
*/
/*    private static void test(Integer[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[right];
        int i = left, j = right - 1;

        while (i <= j){
            while (arr[i] < pivot){
                i++;
            }

            while (j >= 0 && arr[j] > pivot){
                j--;
            }

            if(i <= j){
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        swap(arr, i, right);
        quickSort(arr, left, j);
        quickSort(arr, i + 1, right);
    }*/

/*    private static void test(Integer[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[right];
        int i = left, j = right - 1;

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (j >= 0 && arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        swap(arr, i, right);
        quickSort(arr, left, j);
        quickSort(arr, i + 1, right);
    }*/

    /*private static void test(Integer[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[right];
        int i = left, j = right - 1;

        while (i <= j){
            while (arr[i] < pivot){
                i++;
            }

            while (j >= 0 && arr[j] > pivot){
                j--;
            }

            if(i <= j){
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        swap(arr, i, right);
        quickSort(arr, left, j);
        quickSort(arr, i + 1, right);
    }*/

    /*private static void test(Integer[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[right];
        int i = left, j = right - 1;
        while (i <= j) {
            while (arr[i] < pivot){
                i++;
            }

            while (j >= 0 && arr[j] > pivot){
                j--;
            }

            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        swap(arr, i, right);
        quickSort(arr, left, j);
        quickSort(arr, i + 1, right);
    }
*/
    /*public static void test(Integer[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(Integer[] arr, int left, int right) {
        if(left >= right) return;

        int pivot = arr[right];
        int i = left, j = right - 1;
        while (i <= j){
            while (arr[i] < pivot){
                i++;
            }

            while (j >= 0 && arr[j] > pivot){
                j--;
            }

            if(i <= j){
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        swap(arr, i, right);
        quickSort(arr, left, j);
        quickSort(arr, i + 1, right);

    }*/

/*    private static void quickSort(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[right];

        int i = left, j = right - 1;

        while (i <= j){
            while (arr[i] < pivot){
                i++;
            }

            while (j>=0 &&arr[j] > pivot)  {
                j--;
            }

            if(i <= j){
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        Utils.swap(arr, i, right);
        quickSort(arr, left, j);
        quickSort(arr, i + 1, right);
    }*/








 /*   private static void quickSort(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[right];

        int i = left, j = right - 1;

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (j >= 0 && arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                Utils.swap(arr, i, j);
                i++;
                j--;
            }
        }

        Utils.swap(arr, i, right);
        quickSort(arr, left, j);
        quickSort(arr, i + 1, right);
    }*/

 /*   private static void quickSort(Integer[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[right];
        int i = left, j = right - 1;

        while (i <= j) {
            while (arr[i] < pivot){
                i++;
            }
            while (j >= 0 && arr[j] > pivot){
                j--;
            }

            if(i <= j){
                Utils.swap(arr, i, j);
                i++;
                j--;
            }
        }

        Utils.swap(arr, i, right);
        quickSort(arr, left, j);
        quickSort(arr, i +1, right);
    }*/
}
